import java.util.*;


public class Leetcode675 {
    public static void main(String[] args) {
        System.out.println(cutOffTree(List.of(List.of(1, 2, 3), List.of(0, 0, 4), List.of(7, 6, 5))));
    }

    public static int cutOffTree(List<List<Integer>> forest) {
        List<int[]> trees = new ArrayList<>();
        for (int i = 0; i < forest.size(); i++) {
            for (int j = 0; j < forest.get(0).size(); j++) {
                if (forest.get(i).get(j) > 1) {
                    trees.add(new int[]{forest.get(i).get(j), i, j});
                }
            }
        }

        int[][] treesArray = trees.toArray(new int[0][]);
        Arrays.sort(treesArray, Comparator.comparingInt(a -> a[0]));

        int res = 0;
        int[] pos = new int[]{0, 0};
        for (int[] tree : treesArray) {
            int step = bfs(forest, pos, tree[1], tree[2]);
            if (step == -1) {
                return -1;
            }
            res += step;
            pos[0] = tree[1];
            pos[1] = tree[2];
        }
        return res;
    }

    private static int bfs(List<List<Integer>> forest, int[] start, int targetX, int targetY) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] visited = new int[forest.size()][forest.get(0).size()];
        int[][] dist = new int[forest.size()][forest.get(0).size()];
        for (int i = 0; i < forest.size(); i++) {
            Arrays.fill(visited[i], -1);
            Arrays.fill(dist[i], -1);
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = 0;
        dist[start[0]][start[1]] = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == targetX && cur[1] == targetY) {
                return dist[cur[0]][cur[1]];
            }
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                if (x >= 0 && x < forest.size() && y >= 0 && y < forest.get(0).size() && forest.get(x)
                                                                                               .get(y) > 0 && visited[x][y] == -1) {
                    visited[x][y] = visited[cur[0]][cur[1]] + 1;
                    dist[x][y] = dist[cur[0]][cur[1]] + 1;
                    queue.offer(new int[]{x, y});
                }
            }
        }

        return -1;
    }
}
